Problem statement: zenit13kkk

Posledný problém, ktorý musí Maroško ako prezident vyriešiť predtým, ako dnes pôjde spať je problém farmy s prasiatkami. Farmári by chceli ušetriť čo najviac vody a preto žiadajú o pomoc Maroška.

Farma, ktorej chceme pomôcť poskytuje pre chované prasiatka najvyšší komfort. Každé prasiatko má svoju vlastnú veľkú ohradu so samostatným válovom a samozreme nádobou s vodou, ktorá je neustále dopĺňaná. Na farme sa nachádza niekoľko prívodov, ktoré sú regulované kohútikmi. Letecký snímok farmy vyzerá napríklad takto:

....o..o....o....o..
....|..|....|....|..
....|..|....|....|..
X---------------.|..
...\|..|...\|...\|..
....|..|....|....|..
X----------.|....|..
....|.\|...\|....|..
....|..|....|....|..
....P..P....P....P..

Znaky X označujú kohútik. Vodorovná čiara označuje potrubie, ktorým ide voda z kohútika. Znak o označuje začiatok napájacieho potrubia pre prasiatko a zvislá čiara toto potrubie. Všimnite si, že táto zvislá čiara je prerušovaná vodorovnými. Toto potrubie totiž prechádza popod potrubia vedúce z kohútikov. Napokon, znak P označuje ohradu s prasiatkom. Znak \ označuje, že potrubie z kohútika je napojené na potrubie pre prasiatko.

Kohútiky očíslujeme od 1 smerom zhora dole. Prasiatka očíslujeme 1 smerom zľava doprava. Ak v príklade vyššie otočíme prvý kohútik, voda pritečie prasiatkam 1, 3 a 4, ale nie prasiatku číslo 2.

Našou úlohou je pootáčať kohútiky tak, aby bolo každé prasiatko napojené aspoň jedným kohútikom. Nevadí, ak je napájané viacerými. Zistite, koľko najmenej kohútikov je potrebné otvoriť. V príklade vyššie je odpoveď 2, pretože ani jeden z dvoch kohútikov nedokáže sám napojiť všetky prasiatka.

Na prvom riadku vstupu sú rozmery fotografie R a S. Tieto čísla sú aspoň 6 a nepresahjú 200. Na ďalších R riadkoch je fotografia. Pre fotografiu platí nasledovné:

• Všetky znaky na vstupe budú X,-,|, o,P, \ alebo ., pričom znaky X budú len v prvom stĺpci, znaky o budú len vo vrchnom riadku a znaky P budú len v spodnom riadku.
• Medzi znakmi P bude rozostup aspoň dva a najviac 10 stĺpcov. Medzi znakmi X bude rozostup aspoň dva a najviac 10 riadkov.
• Prvé P bude najskôr vo štvrtom stĺpci a posledné bude najneskôr v predposlednom. Prvé X bude najskôr na treťom riadku a posledné bude najneskôr vo štvrtom od konca.
• Z každého X bude vychádzať vodorovný súvislý pás znakov -, ktorý skončí dva stĺpce pred niektorým zo zvislých potrubií (na toto zvislé potrubie bude daný kohútik napojený). Žiadne iné znaky - na vstupe nebudú.
• Ak je v nejakom stĺpci o, je v tomto stĺpci aj P a opačne. Medzi každým o a P bude stĺpec pozostávajúci zo znakov |. Tento stĺpec môže byť prerušený len znakmi - vo vhodných riadkoch. Iné znaky | na vstupe nebudú.
• Znak \ sa bude vyskytovať výlučne na mieste, ktoré je pod riadkom s potrubím a pred stĺpcom s potrubím. Znak naľavo hore od \ bude vždy -.
• Všetky ostatné znaky na vstupe budú bodky.

Na farme bude aspoň jedno prasiatko a aspoň jeden kohútik. Každé potrubie napája aspoň jedno prasiatko a každé prasiatko je napojené aspoň jedným potrubím. Môžete predpokladať, že kohútikov je najviac 35, prasiatok najviac 60 a tiež môžete predpokladať, že každé prasiatko je napájané najviac štyrmi kohútikmi a že každý kohútik napája najviac štyri prasiatka. Na výstup vypíšte jediné číslo: minimálny počet kohútikov, ktoré treba zapnúť, aby boli napojené všetky prasiatka.

Na testovači máte okrem týchto príkladov ešte dva: sample.02.in má 25 kohútikov a sample.03.in má 35 kohútikov. Riešenie, ktoré úplne priamočiaro skúša všetky možnosti môže získať približne polovicu bodov.

6 9
...o...o.
...|...|.
X-----.|.
..\|..\|.
...|...|.
...P...P.

 

1 

15 22
....o..o....o....o....
....|..|....|....|....
X---------------.|....
...\|..|...\|...\|....
....|..|....|....|....
X---------------.|....
...\|..|...\|...\|....
....|..|....|....|....
X----------.|....|....
....|.\|...\|....|....
....|..|....|....|....
X---------------.|....
....|.\|...\|...\|....
....|..|....|....|....
....P..P....P....P....
 

2